package class8;

import com.sun.jmx.remote.internal.ArrayQueue;
import common.TreeNode;
import common.TreeNodeUtils;

import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * 非递归方式遍历二叉树
 * 1.层序遍历,需要队列进行遍历
 * 2.出队列先打印节点
 * 3.头节点先进队列，再将 左节点 和 右节点 进入队列
 * <p>
 * 题目：
 * 二叉树的最大宽度
 */
public class Code03_BinaryTreeCeng {
    public static void main(String[] args) {
        TreeNode root = TreeNodeUtils.getTreeNode();
        // 层序遍历
        cengOrder(root);
        // 层序遍历返回
        List<List<Integer>> lists = level2(root);
        System.out.println(lists);
    }

    public static void cengOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.print(cur.val + "\t");
            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right != null) {
                queue.add(cur.right);
            }
        }
        System.out.println();
    }

    public static List<List<Integer>> level2(TreeNode treeNode) {
        if (treeNode == null) return null;
        List<List<Integer>> ans = new ArrayList();
        Queue<TreeNode> queue = new LinkedList();
        queue.add(treeNode);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while (size-- > 0) {
                TreeNode poll = queue.poll();
                list.add(poll.val);
                if (poll.left != null) {
                    queue.add(poll.left);
                }
                if (poll.right != null) {
                    queue.add(poll.right);
                }
            }
            ans.add(list);
        }
        return ans;
    }
}
